{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "http://cs229.stanford.edu/ps/ps2/ps2.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ \\theta_{ML} = \\mathrm{arg} \\max_{\\theta} \\prod_{i=1}^{m} p(y^{(i)} | x^{(i)}; \\theta) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ \\theta_{MAP} = \\mathrm{arg} \\max_{\\theta} p(\\theta) \\prod_{i=1}^{m} p(y^{(i)} | x^{(i)}; \\theta)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\theta \\sim \\mathcal{N}(0, \\tau^{2}I)\n",
    "$$\n",
    "\n",
    "where, $\\tau > 0$, and $I$ is the $(n + 1) \\times (n + 1)$ identity matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prove that $$\\left|\\left|\\theta_{MAP}\\right|\\right|_2 \\le \\left|\\left|\\theta_{ML}\\right|\\right|_2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By contradiction:\n",
    "\n",
    "If $$\\left|\\left|\\theta_{MAP}\\right|\\right|_2 \\gt \\left|\\left|\\theta_{ML}\\right|\\right|_2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, because $\\theta$ follows a normal distribution,\n",
    "\n",
    "\\begin{align*}\n",
    "p(\\theta_{MAP}) \\lt p(\\theta_{ML})\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, \n",
    "\n",
    "\\begin{align*}\n",
    "p(\\theta_{MAP}) \\prod_{i=1}^{m}  p(y^{(i)} | x^{(i)}; \\theta_{MAP}) &<  p(\\theta_{ML}) \\prod_{i=1}^{m}  p(y^{(i)} | x^{(i)}; \\theta_{MAP}) \\\\\n",
    "&< p(\\theta_{ML}) \\prod_{i=1}^{m}  p(y^{(i)} | x^{(i)}; \\theta_{ML}) \\\\\n",
    "\\end{align*}\n",
    "\n",
    "The second inequality is due to that $\\theta_{ML}$ maximizes $\\prod_{i=1}^{m} p(y^{(i)} | x^{(i)}; \\theta)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus, it contradicts with that $\\theta_{MAP}$ maximizes $\\prod_{i=1}^{m} p(y^{(i)} | x^{(i)}; \\theta)$. Hence, it has to be \n",
    "\n",
    "$$\n",
    "\\left|\\left|\\theta_{MAP}\\right|\\right|_2 \\le \\left|\\left|\\theta_{ML}\\right|\\right|_2\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
